package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2019/10/20
 * @description:	144. 二叉树的前序遍历
 * 给定一个二叉树，返回它的 前序 遍历。
 *
 *  示例:
 * 输入: [1,null,2,3]
 *    1
 *     \
 *      2
 *     /
 *    3
 *
 * 输出: [1,2,3]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BinaryTreePreorderTraversal144B {

	/**
	 * 通过递归前序遍历(A)
	 * 1ms	97.23
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> preorderTraversalByRecursive(TreeNode root) {
		List<Integer> result=new ArrayList<>();
		if (root==null){
			return result;
		}
		result.add(root.val);
		if (root.left!=null){
			preOrderByRecursive(root.left,result);
		}
		if (root.right!=null){
			preOrderByRecursive(root.right,result);
		}
		return result;
	}

	public void preOrderByRecursive(TreeNode root, List<Integer> list){
		if (root==null){
			return;
		}
		list.add(root.val);
		if (root.left!=null){
			preOrderByRecursive(root.left,list);
		}
		if (root.right!=null){
			preOrderByRecursive(root.right,list);
		}
	}

	/**
	 * 迭代iterative算法
	 * todo:通过深度优先算法。画一下图帮助弄明白
	 * @param root
	 * @return
	 */
	public List<Integer> preorderTraversalByIteratively(TreeNode root){
		List<Integer> result = new ArrayList<>();
		if (root==null){
			return result;
		}
		Stack<TreeNode> stack=new Stack<>();
		stack.add(root);
		while (!stack.isEmpty()){
			TreeNode tempNode=stack.pop();
			result.add(tempNode.val);
			if (tempNode.right!=null){
				stack.add(tempNode.right);
			}
			if (tempNode.left!=null){
				stack.add(tempNode.left);
			}
		}
		return result;
	}

	@Test
	public void testPreorderByRecursive(){
		TreeNode node=new TreeNode(1);
		node.right=new TreeNode(2);
		node.right.left=new TreeNode(3);
		preorderTraversalByRecursive(node);

	}
}
